#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN     60
#define EDGE_NUM (rst->gx)*(rst->gy - 1) + (rst->gy)*(rst->gx - 1)
#define INFTY   65535

void    swap ( int *array, int i, int j )
{
        int     tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
}
int     abs ( int x )
{
        return  x>0?x:-x;
}
int     min ( int x, int y )
{
        return  (x<y)?x:y;
}
int     max ( int x, int y )
{
        return  (x>y)?x:y;
}
//      assign  values to given point
void    assign_point ( point *p, int x, int y)
{
        p->x = x;
        p->y = y;
}
//      return edge id based on two incident point ids 
int     find_edge_id (int x1, int y1, int x2, int y2, routingInst *rst )
{
        int     x,y;
        if ( y1 == y2 )
        {
                y = y1;
                x = min (x1, x2);
                return  ((rst->gx)-1)*y + x;
        }
        else
        {
                x = x1;
                y = min ( y1, y2 );
                return  ((rst->gx)-1)*(rst->gy)+(rst->gx)*y + x;
        }
        return -1;
}
//      print two incident nodes of a given edge id
void    print_net_edges ( FILE *fp, int id, routingInst *rst )
{
        point   p1, p2;
        if ( id <= (rst->gx-1) * rst->gy -1 )
        {
                int     y = id / ( rst->gx - 1 );
                p1.y = y;       p2.y = y;
                int     x = id % ( rst->gx - 1 );
                p1. x = x;      p2.x = x+1;
        }
        else
        {
                id = id - (rst->gx - 1 )*rst->gy;
                int     y = id / rst->gx;
                p1.y = y;       p2.y = y+1;
                int     x = id % rst->gx;
                p1. x = x;      p2.x = x;
        }
        fprintf ( fp, "(%d,%d)-(%d,%d)\n", p1.x, p1.y, p2.x, p2.y );
}       
int     pt_dist ( point p1, point p2 )
{
        return  abs(p1.x - p2.x)+abs(p1.y - p2.y);
}
void    ptr_net ( net *n )
{
        printf ( "numPins = %d\n" , n->numPins );
        for (int i = 0; i<n->numPins; i++)
                printf("point %d : %d\t%d\n", i, n->pins[i].x, n->pins[i].y );
        return;
}
int     is_flat ( point p1, point p2 )
{
        return (p1.x==p2.x)||(p1.y==p2.y);
}
int_LL  *new_int_LL ()
{
        int_LL  *node;
        if (!(node=(int_LL*)malloc(sizeof(int_LL))))
                exit (0);
        node->next = NULL;
        return node;
}
int     *new_array ( int size )
{
        int *array;
        if (!(array=(int*)calloc(size,sizeof(int))))
                exit (0);
        return  array;
}
float   *new_float_array ( int size )
{
        float   *array;
        if (!(array=(float*)calloc(size,sizeof(float))))
                exit (0);
        return  array;
}
void    assign_array ( int *array, int size, int val )
{
        for ( int i = 0; i < size; ++i )
                array[i] = val;
}
int     contain_array ( int *array, int size, int val )
{
        for ( int i = 0; i < size; ++i )
                if ( array[i] == val )
                        return 1;
        return 0;
}
int     non_zero_array ( int *array, int size )
{
        int     cnt = 0;
        for ( int i =0; i<size; i++ )
                if ( array[i] )
                        ++ cnt;
        return cnt;
}
int     find_int_LL ( int edge_id, int_LL *linklist )
{
        int_LL  *node;
        for ( node = linklist; node->next; node=node->next )
                if ( node->next->num == edge_id )
                        return 1;
        return  0;
}
void    insert_int_LL ( int id, int_LL *linklist )
{
        if ( !find_int_LL ( id, linklist ) )
        {
                int_LL  *node = new_int_LL ();
                node->num = id;
                node->next = linklist->next;
                linklist->next = node;
        }
}
void    remove_int_LL ( int id, int_LL *linklist )
{
        if (find_int_LL ( id, linklist ))
        {
                int_LL  *node;
                for ( node = linklist; node->next; node=node->next )
                        if ( node->next->num == id )
                        {
                                node->next = node->next->next;
                                return;
                        }
        }
}
int     length_int_LL ( int_LL *linklist )
{
        int     cnt = 0;
        int_LL  *node;
        for ( node = linklist; node->next; node=node->next )
                cnt ++;
        return  cnt;
}
void    load_int_LL ( int_LL *linklist, routingInst *rst )
{
        int_LL  *node;
        for ( node = linklist; node->next; node=node->next )
                ++ rst->edgeUtils[node->next->num];
}
/* define weight for each edge */
float   dfn_weight ( int util, int cap )
{
//        return  (util>cap)?10*(util-cap)+1:1;
//        return  (util>cap)?(util-cap):0;        // 200 509K 22.30
//        return  (util>cap)?(int)sqrt(util-cap):0;        // 200 501K 19.89
//        return  (util>cap)?(int)sqrt((int)sqrt(util-cap)+1)+1:0;        // 200 496K 17.59
                                                                        // 500 453K 36
//        return  (util>cap)?(int)log(util-cap)+1:0;        // 200 498K 19
//        return  (util>cap)?(int)log(util-cap)+10:0;        // 200 494K 22
//        return  (util>cap)?(util-cap)*(util-cap):0; // 200 523K 13.23
        return  exp(util/(cap+1));
}
/* update the weight information of all the edges in rst */
int     ofl     ( routingInst *rst )
{
        int     ofl=0;
        for (int i=0; i<rst->numEdges; i++)
        {
                rst->edgeWeights[i]= dfn_weight (rst->edgeUtils[i], rst->edgeCaps[i]);
                //      udpate edge weight for A* search
                if ( rst->edgeUtils[i] > rst->edgeCaps[i] )
                {
                        ofl += (rst->edgeUtils[i] - rst->edgeCaps[i]);
                }
        }
        return  ofl;
}
/* connect flat segments and insert edges into edgeUtils */
void    connect_flat ( net *n, point p1, point p2, routingInst *rst )
{
        int     x,y;
//        printf ( "(%d,%d)-(%d,%d)\n", p1.x, p1.y, p2.x, p2.y );
        if ( p1.y == p2.y )
                for ( x = min(p1.x, p2.x); x < max(p1.x, p2.x); x++)
                {
                        int     edge_id = find_edge_id (x,p1.y,x+1,p2.y,rst);
                        if (! find_int_LL ( edge_id, n->edgeUtils ))
                                insert_int_LL ( edge_id, n->edgeUtils );
                }
        if ( p1.x == p2.x )
                for ( y = min(p1.y, p2.y); y < max(p1.y, p2.y); y++)
                {
                        int     edge_id = find_edge_id (p1.x,y,p2.x,y+1,rst);
                        if (! find_int_LL ( edge_id, n->edgeUtils ))
                                insert_int_LL ( edge_id, n->edgeUtils );
                }
}
point   find_corner ( net *n, point p1, point p2, routingInst *rst )
{
        point   tmp;
        tmp.x = p1.x;
        tmp.y = p2.y;
        return  tmp;
}
void    simple_connect ( net *n, int pt1, int pt2, routingInst *rst )
{
        if (is_flat( *(n->pins+pt1), *(n->pins+pt2) ))
                connect_flat ( n, *(n->pins+pt1), *(n->pins+pt2), rst );
        else
        {
                point   tmp = find_corner ( n, *(n->pins+pt1), *(n->pins+pt2), rst );
                connect_flat ( n, *(n->pins+pt1), tmp, rst );
                connect_flat ( n, tmp, *(n->pins+pt2), rst );
        }
}
void    init_net ( net *n, routingInst *rst )
{
        n->edgeUtils = new_int_LL ();
}
void    gen_mst ( net *n, routingInst *rst )
{
        init_net ( n, rst );
        int     NUM = n->numPins;
        int     *inG = new_array(NUM);  // routed pins in net
        int     pt1 = -1;
        int     pt2 = -1;
        for ( int i = 0; i < NUM; i++ )
                inG[i] = 0;

        /* find smallest dist among all the n\choose 2 pairs */
        int     dist = rst->gx + rst->gy;
        int     i, j;
        for ( i= 0; i< NUM-1; ++i )
                for ( j= i+1; j< NUM; ++j )
                        if ( pt_dist(n->pins[i], n->pins[j]) < dist )
                        {
                                dist = pt_dist(n->pins[i],n->pins[j]);
                                pt1 = i;        pt2 = j;
                        }
        inG[pt1] = 1;
        inG[pt2] = 1;
        simple_connect ( n, pt1, pt2, rst );
        /* routing other pins */
        int     k = 1;          
        while ( k < NUM-1 )       /* generate MST */
        {
                /* find the smallest distance */
                int     dist = rst->gx + rst->gy;
                for ( int i = 0; i < NUM; i++)
                        for ( int j = 0; j < NUM; j++)
                                if ( inG[i] && !inG[j] && (pt_dist(n->pins[i],n->pins[j])<dist) )
                                {
                                        dist = pt_dist ( n->pins[i], n->pins[j] );
                                        pt1 = i;        pt2 = j;
                                }
                inG[pt2] = 1;
                simple_connect ( n, pt1, pt2, rst );
                k++;
        }
        load_int_LL ( n->edgeUtils, rst );
}
/* update netWeight in rst */
void    cal_single_netWeight ( int net_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        int_LL  *node;
        int     netWeight = 0;
        for ( node = n->edgeUtils; node->next; node=node->next )
                netWeight += rst->edgeWeights[node->next->num];
        rst->netWeights[net_id] = netWeight; 
}
void    cal_netWeights ( routingInst *rst )
{
        for (int i=0; i<rst->numNets; i++)
                cal_single_netWeight ( i, rst );
}
int     partition ( int *list, int left, int right, float *key )
{
        int     pivot = left;
        int     store_right = right;
        while ( pivot < store_right )
        {
                if ( key[list[pivot]] < key[list[pivot+1]] )
                {
                        swap ( list, pivot, pivot+1 );
                        ++ pivot;
                }
                else
                {
                        swap ( list, pivot+1, store_right );
                        -- store_right;
                }
        }
        return  pivot;
}
void    quicksort ( int *list, int left, int right, float *key )
{
        if ( left < right )
        {
                int     newpivot;
                newpivot = partition ( list, left, right, key );        // pick pivot as left-most element
                if ( left <= newpivot-1 )
                        quicksort ( list, left, newpivot-1, key );
                if ( newpivot+1 <= right )
                        quicksort ( list, newpivot+1, right, key );
        }
}
int     pre_sort ( int *list, int left, int right, float *key )   // push zero-elements to the right
{
        int     pivot = left;
        int     store_right = right;
        while ( pivot < store_right )
        {
                if ( key[list[pivot]] )
                        ++ pivot;
                else
                {
                        swap ( list, pivot, store_right );
                        -- store_right;
                }
        }
        return  pivot;
}
int     *sort_array ( float *weight, int numNets )
{
        int     *sort = new_array ( numNets ); 
        for (int i=0; i < numNets; ++i)
                sort[i] = i;
        int     non_zero_pos = pre_sort ( sort, 0, numNets-1, weight );
        quicksort ( sort, 0, non_zero_pos, weight );
        return  sort;
}
/* rip-up and update all the infomation */
void    rip_up ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        int_LL *node;
        for ( node = n->edgeUtils; node->next; node=node->next )
        {
                int     id = node->next->num;
                -- rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight (rst->edgeUtils[id], rst->edgeCaps[id]);
        }
        n->edgeUtils->next = NULL;
        rst->netWeights[net_id] = 0; 
        load_int_LL ( n->edgeUtils, rst );
        cal_netWeights ( rst );
}

int     pt_to_id ( point pt, routingInst *rst )
{
        return  pt.y*(rst->gx)+pt.x;
}
point   id_to_pt ( int id, routingInst *rst )
{
        point   p;
        p.x = id % (rst->gx);
        p.y = id / (rst->gx);
        return  p;
}
/* input        node id */
/* output       node id */
int_LL  *neighbor ( int id, routingInst *rst, int x_min, int y_min, int x_max, int y_max, int band )
{
        int_LL  *neighbor = new_int_LL();
        point   p = id_to_pt ( id, rst );
        int     gx = rst->gx;
        int     xmin = max (x_min-band, 0);
        int     ymin = max (y_min-band, 0);
        int     xmax = min (x_max+band, rst->gx-1);
        int     ymax = min (y_max+band, rst->gy-1);
        //      test whether all four neighbors exist
        if ( p.x > xmin )          // left neighbor
                insert_int_LL ( p.y * gx + p.x - 1, neighbor );
        if ( p.x < xmax )       // right neighbor
                insert_int_LL ( p.y * gx + p.x + 1, neighbor );
        if ( p.y > ymin )          // down neighbor
                insert_int_LL ( (p.y-1)*gx + p.x, neighbor );
        if ( p.y < ymax )       // up neighbor
                insert_int_LL ( (p.y+1)*gx + p.x, neighbor );
        return  neighbor;
}
//void    reconstruct_path ( int net_id, int *came_from, int size, int start, int goal, routingInst *rst )
void    reconstruct_path ( int  *came_from, int num, int start, int goal, routingInst *rst, net *n, int_LL *to_route )
{
        int     cur = goal;
        while ( cur != start )
        {
                point   p1 = id_to_pt ( cur, rst );
                point   p2 = id_to_pt ( came_from[cur], rst );
                /* determine the edge to add */
                int     edge = find_edge_id ( p1.x, p1.y, p2.x, p2.y, rst );
//                printf ( "(%d,%d)-(%d,%d)\n", p1.x, p1.y, p2.x, p2.y );
                cur = came_from[cur];

                insert_int_LL ( edge, n->edgeUtils );
                insert_int_LL ( cur, n->nodeUtils );
                if (find_int_LL (cur, to_route))
                        remove_int_LL ( cur, to_route );
        }
}
int     weight_between ( int p1, int p2, routingInst *rst )
{
        point   pt1 = id_to_pt ( p1, rst );
        point   pt2 = id_to_pt ( p2, rst );
        int     edge_id = find_edge_id ( pt1.x, pt1.y, pt2.x, pt2.y, rst );
        return  rst->edgeWeights[edge_id];
}
void    A_star_connect ( int net_id, int start, int goal, routingInst *rst, int_LL *to_route )
{
        /* define bounding box */
        point   ps = id_to_pt ( start, rst );
        point   pt = id_to_pt ( goal, rst );
        net     *n = rst->nets + net_id;
//        printf ( "A* search from (%d, %d) to (%d, %d) finished\n", ps.x, ps.y, pt.x, pt.y );

        int     num = rst->gx * rst->gx;
        int     x_min = min ( ps.x, pt.x );
        int     y_min = min ( ps.y, pt.y );
        int     x_max = max ( ps.x, pt.x );
        int     y_max = max ( ps.y, pt.y );
//        int     band = 1;       // 200 453K
//        int     band = 5;       // 200 452K      
        int     band = 2;
        int     xmin = max (x_min-band, 0);
        int     ymin = max (y_min-band, 0);
        int     xmax = min (x_max+band, rst->gx-1);
        int     ymax = min (y_max+band, rst->gy-1);
//        printf ( "\tBounding Box from : (%d, %d) to (%d,%d)\twith size of %d\n", 
//                        xmin, ymin, xmax, ymax, (xmax-xmin+1)*(ymax-ymin+1) );
        /* initialization of A-star search  */
        int_LL  *closedset = new_int_LL();
        int_LL  *openset = new_int_LL();
        insert_int_LL ( start, openset );
        int     *came_from = new_array ( num ); // parents 
        int     *g = new_array ( num );         // cost from start along best known path
        assign_array ( g, num, INFTY);
        g[start] = 0;
        int     *f = new_array ( num );         // estimated total cost from start to goal through v
        assign_array ( f, num, INFTY);
        f[start] = g[start] + pt_dist ( id_to_pt(start,rst), id_to_pt(goal,rst) );
        /* WITH : 200 runs : 509764 22.41s */
        /* WITHOUT : 200 runs : 509764 22.41s */
/* 
        for ( int x = xmin; x <= xmax; x++ )
        {
                for ( int y = ymin; y <= ymax ; y++ )
                {
                        point   p;      p.x = x;        p.y = y;
                        int     pid = pt_to_id ( p, rst );
                        if ( find_int_LL ( pid, n->nodeUtils ) )
                        {
                                g[pid] = 0;
                                f[pid] = g[pid] + pt_dist ( p, id_to_pt(goal,rst) );
                        }
                }
        }
 */
        while ( openset->next )
        {
                int     cur = -1;
                int     dist = INFTY;
                for ( int_LL *node = openset; node->next; node=node->next )
                        if ( f[node->next->num] < dist )
                        {
                                cur = node->next->num;
                                dist = f[cur];
                        }
//                printf ( "cur=%d,%d\n", id_to_pt(cur,rst).x,id_to_pt(cur,rst).y);
//                if ( find_int_LL ( cur, n->nodeUtils ) )
//                        g[cur] = 0;
                if ( cur == goal )
                {
//                        printf ( "shit up\n" );
//                        printf ( "came_from[goal]=%d\tstart=%d\n", came_from[goal], start );
                        reconstruct_path ( came_from, num, start, goal, rst, n, to_route );
                        return;
                }
                remove_int_LL ( cur, openset );
                insert_int_LL ( cur, closedset );
                int_LL  *Adj = neighbor ( cur, rst, xmin, ymin, xmax, ymax, band );
                for ( int_LL *node = Adj; node->next; node=node->next )
                {
                        int     v = node->next->num;
//                        point   p1 = id_to_pt(v,rst);
//                        point   p2 = id_to_pt(cur,rst);
//                        int     e = find_edge_id ( p1.x, p1.y, p2.x, p2.y, rst );
//                        printf ( "edge_id = %d\n", e );
//                        printf ( "edgeUtil = %d\tedgeCap = %d\n", rst->edgeUtils[e], rst->edgeCaps[e] );
//                        printf ( "weight(cur,v)=%d\n", weight_between (cur,v,rst) );
//                        printf ( "neighbor (%d, %d)\n", id_to_pt(v,rst).x, id_to_pt(v,rst).y );
                        int     tmp = g[cur] + weight_between ( cur,v,rst );
//                        printf ( "tmp=%d\tg[v]=%d\n", tmp, g[v] );
                        if ( find_int_LL(v,closedset) && (tmp>=g[v]) )
                                continue;
                        if ( !find_int_LL(v,openset) || (tmp<g[v]) )
                        {
                                came_from[v] = cur;
//                                point p1 = id_to_pt ( v, rst );
//                                point p2 = id_to_pt ( cur, rst );
                                g[v] = tmp;
//                                printf ( "(%d, %d) - (%d, %d)\n", p1.x, p1.y, p2.x, p2.y );
                                f[v] = g[v] + pt_dist(id_to_pt(v,rst), id_to_pt(goal,rst));
                                if ( !find_int_LL (v,openset) )
                                        insert_int_LL ( v, openset );
                        }
                }
        }
        free (g);
        free (f);
        free (came_from);
        free (openset);
        free (closedset);
        return;
}
void    reroute ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        free (n->edgeUtils);
        n->nodeUtils = new_int_LL ();
        n->edgeUtils = new_int_LL ();
        int     NUM = n->numPins;
        int     pt1=0;
        int     pt2=0;
        /* find the smallest dist among n\choose 2 pairs */
        int     dist = rst->gx + rst->gy;
        for ( int i= 0; i< NUM-1; ++i )
                for ( int j= i+1; j< NUM; ++j )
                        if ( pt_dist(n->pins[i], n->pins[j]) < dist )
                        {
                                dist = pt_dist(n->pins[i],n->pins[j]);
                                pt1 = i;        pt2 = j;
                        }
        point   p1 = n->pins[pt1];
        point   p2 = n->pins[pt2];

        int_LL  *to_route = new_int_LL();       // pins to be routed
        for ( int i = 0; i < NUM; i++ )
                insert_int_LL ( pt_to_id ( n->pins[i], rst ), to_route );

        insert_int_LL ( pt_to_id(p1,rst), n->nodeUtils );
        insert_int_LL ( pt_to_id(p2,rst), n->nodeUtils );
        remove_int_LL ( pt_to_id(p1,rst), to_route );
        remove_int_LL ( pt_to_id(p2,rst), to_route );

//        printf ( "\n(%d,%d)-(%d,%d)\tdist=%d\n", p1.x, p1.y, p2.x, p2.y, dist );
        A_star_connect ( net_id, pt_to_id(n->pins[pt1], rst), pt_to_id(n->pins[pt2], rst), rst, to_route );
        while ( to_route->next )
        {
                /* find the smallest distance */
                dist = INFTY; // initial with possible max dist
                for ( int i = 0; i < NUM; i++)
                        for ( int j = 0; j < NUM; j++)
                        {
                                if (   find_int_LL( pt_to_id(n->pins[i],rst), n->nodeUtils ) && find_int_LL( pt_to_id(n->pins[j],rst), to_route )  
                                        && (pt_dist( n->pins[i], n->pins[j] ) < dist) )
                                {
                                        dist = pt_dist(n->pins[i],n->pins[j]);
                                        pt1 = i;        pt2 = j;
                                }
                        }
                remove_int_LL ( pt_to_id(n->pins[pt2],rst), to_route );
                insert_int_LL ( pt_to_id(n->pins[pt2],rst), n->nodeUtils );
                /* find shortest route between pt1 and pt2 using A-star search */
                p1 = n->pins[pt1];
                p2 = n->pins[pt2];
                A_star_connect ( net_id, pt_to_id(n->pins[pt1], rst), pt_to_id(n->pins[pt2], rst), rst, to_route );
//                printf ( "\n(%d,%d)-(%d,%d)\tdist=%d\n", p1.x,p1.y,p2.x,p2.y,dist );
        }
        load_int_LL ( n->edgeUtils, rst );
        cal_netWeights ( rst );
        return;
}

void    print_single_net ( FILE *fp, int net_id, routingInst *rst )
{
        int_LL *node;
        net     *n = rst->nets + net_id;
        fprintf ( fp, "n%d\n", net_id );
        for (node=n->edgeUtils; node->next; node=node->next )
                print_net_edges ( fp, node->next->num, rst );
        fprintf ( fp, "!\n" );
}
void    print_result ( FILE *fp, routingInst *rst )
{
        printf ( "\n\nWriting Results : ...\nthis may also take time because I haven't optimized it.\n" );
        for ( int i = 0; i<rst->numNets; i++)
                print_single_net ( fp, i, rst );
}
int     tot ( routingInst *rst )
{
        int     TOT = 0;
        for ( int i = 0; i < rst->numNets; i++ )
                TOT += length_int_LL ( rst->nets[i].edgeUtils );
        return  TOT;
}
